/*
	排列问题: 打印数组里元素的全排列
	递归算法
	R = {r1,r2,r3,....,rn}
	Ri = R - {i}
	对X集合进行排列,Perm(X)
	(ri)Perm(X)，表示对X的全排列的最前面加上ri

	example :
	ri = d
	X = {a,b,c}
	Perm(X) = abc, acb, bac, bca, cab, cba
	(ri)Perm(X) = dabc, dacb, dbac, dbca, dcab, dcba

	递归思想:  n为元素个数
	n = 1  Perm(R) = R
	n > 1  Perm(R) = (r1)Perm(R1), (r2)Perm(R2), (r3)Perm(R3),..., (rn)Perm(Rn)
*/

#include <stdio.h>
typedef int ElemType;



void swap(ElemType *a,ElemType *b)
{
	ElemType tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void Perm(ElemType list[], int f, int l)
{//f是数组的第一个位置初始0, l最后一个位置即 长度 - 1

	if (f == l)
	{//递归的边界条件 即n = 1
		for (int i = 0; i <= l; i++)
		{
			printf("%d", list[i]);
		}

		printf("\n");
	}
	else
	{	
		//Perm(list, f+1, l);

		for (int i = f; i <= l; i++)
		{
			if (f != i)
				swap(&list[f],&list[i]);

			Perm(list, f+1, l);

			if (f != i)
				swap(&list[i],&list[f]);			
		}
	}
}

int main(void)
{
	ElemType a[3] = {1,2,3};
	Perm(a,0,2);
}